int B = 200;
int n, m, a[N], h[N];
vector<int> g[N];
int st[N], top, blo[N], idx, fa[N][16], dep[N], dfn[N], dfs_clock;
void dfs(int u, int p, int d) {
	fa[u][0] = p; dep[u] = d;
	dfn[u] = ++dfs_clock;
	for (int i = 1; i < 16; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == p) continue;
		dfs(v, u, d + 1);
		if (top >= B) {
			++idx;
			while (top) blo[st[--top]] = idx;
		}
	}
	st[top++] = u;
}
struct Query {
	int u, v, id;
	void read(int id) {
		this->id = id;
		scanf("%d%d", &u, &v);
		if (blo[u] > blo[v]) swap(u, v);
	}
	bool operator < (const Query &c) const {
		if (blo[u] == blo[c.u]) return dfn[v] < dfn[c.v];
		return blo[u] < blo[c.u];
	}
} q[N];
int ans[N], Ans, cnt[N], vis[N];
void cao(int u) {
	if (vis[u] && (--cnt[a[u]] == 0)) Ans--;
	else if (!vis[u] && (cnt[a[u]]++ == 0)) Ans++;
	vis[u] ^= 1;
}
void gao(int u, int v) {
	int p = lca(u, v);
	while (u != p) cao(u), u = fa[u][0];
	while (v != p) cao(v), v = fa[v][0];
}
int main() {
	B = sqrt(n * 1.0);
	dfs_clock = idx = 0;
	dfs(1, 1, 0);
	++idx;
	while (top) blo[st[--top]] = idx;
	for (int i = 0; i < m; i++) q[i].read(i);
	sort(q, q + m);
	Ans = 0;
	memset(cnt, 0, sizeof(cnt));
	memset(vis, 0, sizeof(vis));
	gao(q[0].u, q[0].v);
	int p = lca(q[0].u, q[0].v);
	cao(p);
	ans[q[0].id] = Ans;
	cao(p);
	for (int i = 1; i < m; i++) {
		gao(q[i - 1].u, q[i].u);
		gao(q[i - 1].v, q[i].v);
		p = lca(q[i].u, q[i].v);
		cao(p);
		ans[q[i].id] = Ans;
		cao(p);
	}
	for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
	return 0;
}
